package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.list.singly.ListNode;
import leetcode.editor.cn.util.list.singly.ListUtil;

/**
 * @author qidi
 * @date 2022-01-18 10:51:29
 */
class Q0148_SortList {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;

            return process(head, null);
        }

        private ListNode process(ListNode start, ListNode end) {
            if (start.next == end) {
                start.next = null;
                return start;
            }

            ListNode slow = start;
            ListNode fast = start;
            while (fast != end) {
                slow = slow.next;
                fast = fast.next;
                if (fast != end) {
                    fast = fast.next;
                }
            }

            ListNode mid = slow;
            ListNode left = process(start, mid);
            ListNode right = process(mid, end);


            ListNode head = new ListNode();
            ListNode cur = head;

            while (left != null && right != null) {
                if (left.val > right.val) {
                    cur.next = right;
                    right = right.next;
                } else {
                    cur.next = left;
                    left = left.next;
                }
                cur = cur.next;
            }

            if (left != null)
                cur.next = left;

            if (right != null)
                cur.next = right;

            return head.next;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0148_SortList().new Solution();
        ListUtil util = ListUtil.getInstance();
        System.out.println(solution.sortList(util.generateFromArray(4, 2, 1, 3)));
        System.out.println(solution.sortList(util.generateFromArray(-1, 5, 3, 4, 0)));
    }
}